package leetcode.code0637;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.tree.TreeNode;

/**

 */
public class Solution2 {
	public List<Double> averageOfLevels(TreeNode root) {
		List<Long> cnts = new ArrayList<>();
		List<Long> sums = new ArrayList<>();
		dfs(root, 0, cnts, sums);
		List<Double> ans = new ArrayList<>();
		for (int i = 0; i < cnts.size(); i++) {
			ans.add((1d * sums.get(i)) / cnts.get(i));
		}
		return ans;
	}

	private void dfs(TreeNode root, int i, List<Long> cnts, List<Long> sums) {
		if (root == null) {
			return;
		}
		if (i < cnts.size()) {
			cnts.set(i, cnts.get(i) + 1);
			sums.set(i, sums.get(i) + root.val);
		} else {
			cnts.add(1l);
			sums.add(1l *root.val);
		}
		dfs(root.left, i + 1, cnts, sums);
		dfs(root.right, i + 1, cnts, sums);
	}
}
